import java.util.HashSet;
import java.util.List;
import java.util.Set;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class project {
    TreeNode node=null;
    boolean bool=false;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root,p);
        return node;
    }
    public void dfs(TreeNode root,TreeNode p){
        if(root==null){
            return;
        }
        dfs(root.left,p);
        if(node==null&&bool){
            node=root;
        }
        if(root.val==p.val){
            bool=true;
        }
        dfs(root.right,p);
    }














    public int minPathSum(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(i==0&&j==0){
                    continue;
                }
                if(i==0){
                    grid[i][j]+=grid[i][j-1];
                }else if(j==0){
                    grid[i][j]+=grid[i-1][j];
                }else{
                    grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
                }
            }
        }
        return grid[row-1][col-1];
    }













    public int minPathSum1(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(i==0&&j==0){
                    continue;
                }
                if(i==0){
                    grid[i][j]+=grid[i][j-1];
                }else if(j==0){
                    grid[i][j]+=grid[i-1][j];
                }else{
                    grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
                }
            }
        }
        return grid[row-1][col-1];
    }















    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> set=new HashSet<>();
        for(String s : dictionary){
            set.add(s);
        }
        StringBuilder sb=new StringBuilder();
        for(String s : sentence.split("\\s+")){
            String str="";
            for(int i=1;i<=s.length();i++){
                str=s.substring(0,i);
                if(set.contains(str)){
                    break;
                }
            }
            if(sb.length()>0){
                sb.append(" ");
            }
            sb.append(str);
        }
        return sb.toString();
    }
















    public String replaceWords1(List<String> dictionary, String sentence) {
        Set<String> set=new HashSet<>();
        for(String str : dictionary){
            set.add(str);
        }
        StringBuilder sb=new StringBuilder();
        for(String s : sentence.split("\\s+")){
            String str="";
            for(int i=1;i<=s.length();i++){
                str=s.substring(0,i);
                if(set.contains(str)){
                    break;
                }
            }
            if(sb.length()>0){
                sb.append(" ");
            }
            sb.append(str);
        }
        return sb.toString();
    }















    public TreeNode pruneTree(TreeNode root) {
        if(root==null){
            return null;
        }
        root.left=pruneTree(root.left);
        root.right=pruneTree(root.right);
        if(root.val==0&&root.left==null&&root.right==null){
            root=null;
        }
        return root;
    }













    public TreeNode pruneTree1(TreeNode root) {
        if(root==null){
            return null;
        }
        root.left=pruneTree1(root.left);
        root.right=pruneTree1(root.right);
        if(root.val==0&&root.left==null&&root.right==null){
            root=null;
        }
        return root;
    }















    public int maxValue(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(i==0&&j==0){
                    continue;
                }
                if(i==0){
                    grid[i][j]+=grid[i][j-1];
                }else if(j==0){
                    grid[i][j]+=grid[i-1][j];
                }else{
                    grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1]);
                }
            }
        }
        return grid[row-1][col-1];
    }













    public int countSubstrings(String s) {
        int res=0;
        for(int i=0;i<s.length();i++){
            for(int j=0;j<=1;j++){
                int left=i;
                int right=i+j;
                while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
                    left--;
                    right++;
                    res++;
                }
            }
        }
        return res;
    }
















    public int countSubstrings1(String s) {
        int sum=0;
        int len=s.length();
        for(int i=0;i<len;i++){
            for(int j=0;j<=1;j++){
                int left=i;
                int right=i+j;
                while(left>=0&&right<len&&s.charAt(left)==s.charAt(right)){
                    sum++;
                    left--;
                    right++;
                }
            }
        }
        return sum;
    }
}
